package com.zwj.interview.动态规划;

/**
 * @Author: Zwj
 * @Date: 2022/2/25 17:47
 * <p>
 * 给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
 * <p>
 * 请你返回让 s 成为回文串的 最少操作次数 。
 * <p>
 * 「回文串」是正读和反读都相同的字符串。
 */
public class 字符串成为回文串的最少插入次数 {

    //dp[i,j]表示字符串s[i..j],最少需要进行dp[i][j]次插入才能成为回文串
    public int minInsertions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        //因为这里我们要求出dp[0][n-1]的值，所以我们从下向上遍历
        for (int i = n - 2; i >= 0; i--) {
            //从左向右遍历
            for (int j = i + 1; j < n; j++) {
                //s[i]==s[j]时，那么就缩小范围
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    /**
                     * 不相等时，那么就先将[i+1..j]或者[i..j-1]变成回文串，此时要[i..j]成为回文串，只要再一次操作就可以使得
                     * [i..j]成为回文串
                     *
                     * 当[i+1,j]或者[i,j-1]之间的字符成为回文串了，那么只要再操作一次(再插入一个字符就可以了)，所以后面加了1
                     */
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) +1;
                }
            }
        }
        return dp[0][n - 1];
    }

}